frequency table
When there are N numbers and N is too large to do O(N^2)
If the order of the numbers is meaningless and the number type is M, which is much less than N
Creating a frequency table by type can reduce the amount of calculations.
Frequency→Triangular number
For any pair of two choices of N numbers, the case where two have the same value is counted
A naive loop is O(N^2)
Count the frequencies and for each value frequency n trigonometric number $ T_{n-1} = n(n-1)/2.
This would be O(N)
multiset 、multiset
---
This page is auto-translated from /nishio/頻度表. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.